|
An endgame tablebase is a computerized database that contains precalculated exhaustive analysis of chess endgame positions. It is typically used by a computer chess engine during play, or by a human or computer that is retrospectively analysing a game that has already been played. The tablebase contains the game-theoretical value (win, loss, or draw) of each possible move in each possible position, and how many moves it would take to achieve that result with perfect play. Thus, the tablebase acts as an oracle, always providing the optimal moves. Typically the database records each possible position with certain pieces remaining on the board, and the best moves with White to move and with Black to move. Tablebases are generated by retrograde analysis, working backwards from a checkmated position. By 2005, all chess positions with up to six pieces (including the two kings) had been solved. By August 2012, tablebases had solved chess for every position with up to seven pieces (the positions with a lone king versus a king and five pieces were omitted because they were considered uninteresting).〔(EGTBs Chessprogramming website )〕〔(【引用サイトリンク】work=ChessOK )〕 The solutions have profoundly advanced the chess community's understanding of endgame theory. Some positions which humans had analyzed as draws were proven to be winnable; the tablebase analysis could find a mate in more than five hundred moves, far beyond the horizon of humans, and beyond the capability of a computer during play. For this reason, they have also called into question the 50 move rule since many positions are now seen to exist that are a win for one side but would be drawn because of the 50 move rule. Tablebases have enhanced competitive play and facilitated the composition of endgame studies. They provide a powerful analytical tool. While endgame tablebases for other board games like checkers,〔(Website ) of KingsRow about the creation of a tablebases for 8x8 and 10x10 checkers〕 chess variants〔(gothicchess.com ); examples of long endings for Gothic chess〕 or Nine Men's Morris〔(【引用サイトリンク】title=Solving nine men's morris )〕 exist, when a game is not specified, it is assumed to be chess. == Background == Physical limitations of computer hardware aside, in principle it is possible to solve any game under the condition that the complete state is known and there is no random chance. Strong solutions, i.e. algorithms that can produce perfect play from any position, are known for some simple games such as Tic Tac Toe (draw with perfect play) and Connect Four (first player wins). Weak solutions exist for somewhat more complex games, such as checkers (with perfect play on both sides the game is known to be a draw, but it is not known for every position created by less-than-perfect play what the perfect next move would be). Other games, such as chess (from the starting position) and Go, have not been solved because their game complexity is too vast for computers to evaluate all possible positions. To reduce the game complexity, researchers have modified these complex games by reducing the size of the board, or the number of pieces, or both. Computer chess is one of the oldest domains of artificial intelligence, having begun in the early 1930s. Claude Shannon proposed formal criteria for evaluating chess moves in 1949. In 1951, Alan Turing designed a primitive chess playing program, which assigned values for material and mobility; the program "played" chess based on Turing's manual calculations.〔Levy & Newborn, pp. 25-38〕 However, even as competent chess programs began to develop, they exhibited a glaring weakness in playing the endgame. Programmers added specific heuristics for the endgame – for example, the king should move to the center of the board.〔Levy & Newborn, pp. 129-30〕 However, a more comprehensive solution was needed. In 1965, Richard Bellman proposed the creation of a database to solve chess and checkers endgames using retrograde analysis.〔Stiller, p. 84〕 Instead of analyzing ''forward'' from the position currently on the board, the database would analyze ''backward'' from positions where one player was checkmated or stalemated. Thus, a chess computer would no longer need to analyze endgame positions during the game because they were solved beforehand. It would no longer make mistakes because the tablebase always played the best possible move. In 1970, Thomas Ströhlein published a doctoral thesis〔See also 〕 with analysis of the following classes of endgame: , , , , , and . In 1977 Thompson's KQKR database was used in a match versus Grandmaster Walter Browne. Ken Thompson and others helped extend tablebases to cover all four- and five-piece endgames, including in particular , , and .〔Levy & Newborn, p. 144〕〔See also: * * 〕 Lewis Stiller published a thesis with research on some six-piece tablebase endgames in 1995.〔Stiller, pp. 68-113〕〔See also: 〕 More recent contributors have included the following people: * Eugene Nalimov, after whom the popular Nalimov tablebases are named; * Eiko Bleicher, who has adapted the tablebase concept to a program called "Freezer" (see below); * Guy Haworth, an academic at the University of Reading, who has published extensively in the ICGA Journal and elsewhere; * Marc Bourzutschky and Yakov Konoval, who have collaborated to analyze endgames with seven pieces on the board; * Peter Karrer, who constructed a specialized seven-piece tablebase () for the endgame of the Kasparov versus The World online match; * Vladimir Makhnychev and Victor Zakharov from Moscow State University, who completed 4+3 DTM-tablebases (525 endings including KPPPKPP) in July 2012. The tablebases are named Lomonosov tablebases. The next set of 5+2 DTM-tablebases (350 endings including KPPPPKP) was completed during August 2012. The high speed of generating the tablebases was because of using a supercomputer named Lomonosov ((top500 )). The size of all tablebases up to seven-man is about 140 TB.〔(【引用サイトリンク】 title=Lomonosov Endgame Tablebases )〕 The tablebases of all endgames with up to six pieces are available for free download, and may also be queried using web interfaces (see the external links below). Nalimov tablebase requires more than one terabyte of storage space. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Endgame tablebase」の詳細全文を読む スポンサード リンク
|